\documentclass[draft]{llncs}[11pt]
\def\isanonymous{0}

\usepackage{ifthen}


\newcommand{\anonymous}[2]{
\ifthenelse{\equal{\isanonymous}{1}}
{{#1}}
{{#2}}
}

\usepackage[utf8x]{inputenc}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{relsize}
\usepackage{xspace}
\usepackage{comment}
\usepackage{tikz,pgfplots}

\usepackage{fullpage}
\usepackage{url}
\usepackage[vlined]{algorithm2e}


\newtheorem{assumption}{Assumption}

\newcommand{\tildeO}[1]{\ensuremath{\tilde{\mathcal{O}}(#1)}\xspace}

\newcommand{\heading}[1]{{\vspace{6pt}\noindent\sc{#1.}}}

\newcommand{\bigO}[1]{\ensuremath{\mathcal{O}\left(#1\right)}\xspace}
\newcommand{\poly}{ {\rm poly}(n)}
\newcommand{\chig}{\ensuremath{\chi_{\alpha,q}}}
\newcommand{\U}{\ensuremath{\mathcal{U}\xspace}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}\xspace}
\newcommand{\Zq}{\ensuremath{\mathbb{Z}_q}\xspace}
\newcommand{\Ldis}{L_{\mathbf{s},\chi}}
\newcommand{\Bdis}[1]{B_{\mathbf{s},\chi,#1}}
\newcommand{\sample}{\ensuremath{\leftarrow_{\$}}}

\newcommand{\CDF}{\ensuremath{\textnormal{CDF}}}
\newcommand{\E}{\ensuremath{\textnormal{E}}}
\newcommand{\Var}{\ensuremath{\textnormal{Var}}}
\newcommand{\Sample}{\ensuremath{\mathbf{Sample}}\xspace}

\newcommand{\abs}[1]{\ensuremath{|#1|}\xspace}

\newcommand{\avec}{\ensuremath{\mathbf{a}}\xspace}
\newcommand{\svec}{\ensuremath{\mathbf{s}}\xspace}
\newcommand{\tvec}{\ensuremath{\mathbf{t}}\xspace}
\newcommand{\vvec}{\ensuremath{\mathbf{v}}\xspace}

\newcommand{\sol}{\ensuremath{(s_{n-w},\dots,s_{n-1})}\xspace}
\newcommand{\solvec}{\ensuremath{\mathbf{s'}}\xspace}

\newcommand{\dotp}[2]{\ensuremath{\langle {#1},{#2}\rangle}\xspace}
\newcommand{\N}[1]{\ensuremath{\mathcal{N}({#1)}}}
\newcommand{\PrS}{\ensuremath{\epsilon}}


\def\abn{\lceil n/b \rceil}
\def\gnd{\left\lceil\frac{n}{d}\right\rceil}

\DeclareMathOperator{\erf}{erf}

\newcommand{\lowerbound}{\ensuremath{\lceil -q/2 \rceil}\xspace}
\newcommand{\upperbound}{\ensuremath{\lfloor q/2\rfloor}\xspace}

\title{On the Complexity of the BKW Algorithm on LWE}
\anonymous{}{
\author{Martin R.~Albrecht \inst{1} \and Carlos Cid \inst{3} \and Jean-Charles Faugère \inst{2} \and Robert Fitzpatrick \inst{3} \and Ludovic Perret \inst{2}}
\institute{
Technical University of Denmark, Denmark \and
INRIA, Paris-Rocquencourt Center, POLSYS Project\\
UPMC Univ Paris 06, UMR 7606, LIP6, F-75005, Paris, France\\
CNRS, UMR 7606, LIP6, F-75005, Paris, France \and
Information Security Group\\
Royal Holloway, University of London\\
Egham, Surrey TW20 0EX, United Kingdom \\ 
\email{maroa@dtu.dk, carlos.cid@rhul.ac.uk, jean-charles.faugere@inria.fr, robert.fitzpatrick.2010@live.rhul.ac.uk, ludovic.perret@lip6.fr}  
}}


\def\nonzerocorr{\frac{q^d}{q^d-1}}

\def\naddssteponeexactT{\left(\frac{q^b-1}{2}\right)\cdot \left( \frac{a(a-1)}{2}\cdot (n+1) - \frac{ba(a-1)}{4}-\frac{b}{6}\left((a-1)^3+\frac{3}{2}(a-1)^2+\frac{1}{2}(a-1)\right) \right)}

\def\naddssteponeexactM{m\cdot\left(\frac{a}{2}\cdot(n+2)\right)}

\def\naddssteponeT{\left(\frac{q^b-1}{2}\right)\cdot \left(  \frac{a(a-1)}{2}\cdot (n+1) \right)}
\def\naddssteponeM{m\cdot(\frac{a}{2}\cdot(n+2))}

\def\ncallsT{a\cdot \left\lceil \frac{q^b}{2}\right\rceil}
\def\ncallsM{m}
\def\nstore{\left( \frac{q^b}{2} \right) \cdot a\cdot \left(n+1 - b\frac{a-1}{2}\right)}

\def\naddssteptwo{{m \cdot q^d}}

\parindent 0em
\parskip 0.9em

\begin{document}

\maketitle

\begin{abstract}
This work presents a study of the complexity of the Blum-Kalai-Wasserman (BKW) algorithm when applied to the Learning with Errors (LWE) problem, by providing refined estimates for the data and computational effort requirements for solving \emph{concrete} instances of the LWE problem. We apply this refined analysis to suggested parameters for various LWE-based cryptographic schemes from the literature and compare with alternative approaches based on lattice reduction. As a result, we provide new upper bounds for the concrete hardness of these LWE-based schemes.
Rather surprisingly, it appears  that BKW algorithm outperforms known estimates for lattice reduction algorithms starting in dimension $n \approx 250$ when LWE is reduced to SIS. However, this assumes access to an unbounded number of LWE samples.
\end{abstract}

\input{intro.tex}

\input{algorithm.tex}

\input{parameters.tex}

\input{comparisons.tex}

\input{implementation.tex}

\section{Conclusion and Further Work}
In this work we have provided a concrete analysis of the cost of running the BKW algorithm on LWE instances both for the search and the decision variants of the LWE problem. We also applied this analysis to various sets of parameters found in the literature. From this we conclude that the BKW algorithm outperforms lattice reduction algorithms in an SIS setting for the parameter sets proposed in \cite{regev:acm09,LindnerP10} starting around dimension $n\approx 250$ at the cost of requiring many more samples and storage. On the other hand, lattice reduction in a BDD setting currently outperforms the BKW algorithm as analysed in this work.

A pressing research question for future work is hence how to apply a variant of the BKW algorithm to the BDD problem. Furthermore, in this work we ignore the so-called LWE ``normal form'' where the secret follows the noise distribution $\chi$ (cf.\ \cite{brakerski-langlois-peikert-regev-stehle:stoc13}) and other small secret variants of LWE. For the BKW algorithm as presented in this work, only hypothesis testing is affected by the size of the secret and hence we do not expect the algorithm to benefit from considering small secrets. Yet, a dedicated variant of the BKW algorithm tackling small secrets is a promising research direction.

\anonymous{}
{\section*{Acknowledgements} We are grateful to Frederik Johansson for advice on numerical integration. We are also grateful to anonymous referees whose feedback substantially improved this work. The work described in this paper has been partially supported by the Royal Society grant JP090728 and by the Commission of the European Communities through the ICT program under contract ICT-2007-216676 (ECRYPT-II).
Jean-Charles Faugère, and Ludovic Perret are also supported by the Computer Algebra and Cryptography (CAC) project (ANR-09-JCJCJ-0064-01) and the HPAC project (HPAC ANR-11-BS02-013) 
of the French National Research Agency.
}
\clearpage
\bibliographystyle{plain}
\bibliography{../StructuredNoise/struct.bib}

\clearpage
\appendix








\end{document}

